#ifndef _MY_STACK_TCC
#define _MY_STACK_TCC

#include <iostream>

template<typename T>
void my_stack<T>::push(const T& data) {
	node<T>* const newNode = new node<T>(data);
	newNode->next = head.load();
	while (!head.compare_exchange_weak(newNode->next, newNode));
}

template<typename T>
shared_ptr<T> my_stack<T>::pop() {
	++nbInPops;
	node<T>* oldHead = head.load();
	while (oldHead && !head.compare_exchange_weak(oldHead, oldHead->next));
	shared_ptr<T> result;
	if (oldHead) {
		result.swap(oldHead->data);
	}
	tryReclaim(oldHead);
	return result;
}

template<typename T>
void my_stack<T>::deleteNodes(node<T>* nodes) {
	while (nodes) {
		node<T>* const next = nodes->next;
		delete nodes;
		nodes = next;
	}
}

template<typename T>
void my_stack<T>::chainPendingNodes(node<T>* first, node<T>* last) {
	last->next = pendingNodes;
	while (!pendingNodes.compare_exchange_weak(last->next, first));
}

template<typename T>
void my_stack<T>::chainPendingNodes(node<T>* n) {
	node<T>* last = n;
	while (node<T>* next = last->next) {
		last = next;
	}
	chainPendingNodes(n, last);
}

template<typename T>
void my_stack<T>::chainPendingNode(node<T>* n) {
	chainPendingNodes(n, n);
}

template<typename T>
void my_stack<T>::tryReclaim(node<T>* oldHead) {
	if (nbInPops == 1) {
		/** Dans ce cas, aucun autre thread n'a accès à oldHead*/
		node<T>* const nodesToBeDeleted = pendingNodes.exchange(nullptr);
		if (!--nbInPops) {
			/** Dans ce cas, aucun autre thread n'a accès à nodesToBeDeleted */
			deleteNodes(nodesToBeDeleted);
		} else if (nodesToBeDeleted) {
			/** S'il y a des noeuds à supprimer, il faut les renchaîner */
			chainPendingNodes(nodesToBeDeleted);
		}
		delete oldHead;
	} else {
		chainPendingNode(oldHead);
		--nbInPops;
	}
}

template<typename T>
void my_stack<T>::afficher() const {
	node<T>* current = head.load();
	while (current) {
		cout << *current->data << " ";
		current = current->next;
	}
	cout << endl;
}

template<typename T>
my_stack<T>::~my_stack() {
	if (head) {
		deleteNodes(head);
	}
	if (pendingNodes) {
		deleteNodes(pendingNodes);
	}
}

#endif
